//单词拆分（medium）:https://leetcode.cn/problems/word-break/description/
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
        unordered_set<string> hash;
        for (auto& s : wordDict)
            hash.insert(s);
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;                // 保证后续填表是正确的
        s = ' ' + s;                 // 使原始字符串的下标统⼀ +1
        for (int i = 1; i <= n; i++) // 填 dp[i]
        {
            for (int j = i; j >= 1; j--) // 最后⼀个单词的起始位置
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break; // 优化⼆
                }
            }
        }
        return dp[n];
    }
};

//环绕字符串中唯⼀的⼦字符串（medium）: https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        // 1. 利⽤ dp 求出每个位置结尾的最⻓连续⼦数组的⻓度
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
            if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] = dp[i - 1] + 1;

        // 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度
        int hash[26] = {0};
        for (int i = 0; i < n; i++)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        // 3. 将结果累加起来
        int sum = 0;
        for (auto x : hash)
            sum += x;

        return sum;
    }
};